package com.learn.algorithm.dynamic.programming;

import java.util.Arrays;

public class LeetCode516 {

    public static int longestPalindromeSubseq(String str) {
        char[] s = str.toCharArray();
        int n = str.length();
        int[][] dp = new int[n][n];
        for (int l = n - 1; l >= 0; l--) {
            dp[l][l] = 1;
            if (l + 1 < n) {
                dp[l][l + 1] = s[l] == s[l + 1] ? 2 : 1;
            }
            for (int r = l + 2; r < n; r++) {
                dp[l][r] = s[l] == s[r] ? 2 + dp[l + 1][r - 1] : Math.max(dp[l + 1][r], dp[l][r - 1]);
            }
        }
        return dp[0][n - 1];
    }

    public static int longestPalindromeSubseq2(String str) {
        int n = str.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        return f2(str.toCharArray(), 0, str.length() - 1, dp);
    }

    public static int f2(char[] s, int i, int j, int[][] dp) {
        if (i == j) {
            return 1;
        }
        if (i + 1 == j) {
            return s[i] == s[j] ? 2 : 1;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }

        int ans;
        if (s[i] == s[j]) {
            ans = 2 + f2(s, i + 1, j - 1, dp);
        } else {
            ans = Math.max(f2(s, i + 1, j, dp), f2(s, i, j - 1, dp));
        }
        dp[i][j] = ans;
        return ans;
    }

    public static int longestPalindromeSubseq1(String str) {
        return f1(str.toCharArray(), 0, str.length() - 1);
    }

    public static int f1(char[] s, int i, int j) {
        if (i == j) {
            return 1;
        }
        if (i + 1 == j) {
            return s[i] == s[j] ? 2 : 1;
        }
        int ans;
        if (s[i] == s[j]) {
            ans = 2 + f1(s, i + 1, j - 1);
        } else {
            ans = Math.max(f1(s, i + 1, j), f1(s, i, j - 1));
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));
        System.out.println(longestPalindromeSubseq("cbbd"));
    }
}
